package code.classic150on2025;

import java.util.*;

public class ArrayAndString {
    // 88. 合并两个有序数组
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int[] tempNums1 = new int[m];
        for (int i = 0; i < m; i++) {
            tempNums1[i] = nums1[i];
        }
        int pos1 = 0, pos2 = 0;
        int pos = 0;
        while (pos1 < m && pos2 < n) {
            if (tempNums1[pos1] < nums2[pos2]) {
                nums1[pos] = tempNums1[pos1];
                pos1++;
            } else {
                nums1[pos] = nums2[pos2];
                pos2++;
            }
            pos++;
        }
        while (pos1 < m) {
            nums1[pos] = tempNums1[pos1];
            pos1++;
            pos++;
        }
        while (pos2 < n) {
            nums1[pos] = nums2[pos2];
            pos2++;
            pos++;
        }
    }

    // 27. 移除元素
    public int removeElement(int[] nums, int val) {
        int len = nums.length;
        int iter = 0;
        int pos = 0;
        int removeNum = 0;
        while (iter < len) {
            if (nums[iter] == val) {
                removeNum++;
            } else {
                nums[pos] = nums[iter];
                pos++;
            }
            iter++;
        }
        return len - removeNum;
    }

    // 26. 删除有序数组中的重复项
    public int removeDuplicates(int[] nums) {
        int len = nums.length;
        int iter = 1;
        int pos = 1;
        int removeNum = 0;
        while (iter < len) {
            if (nums[iter] == nums[iter - 1]) {
                removeNum++;
            } else {
                nums[pos] = nums[iter];
                pos++;
            }
            iter++;
        }
        return len - removeNum;
    }

    // 80. 删除有序数组中的重复项 II
    public int removeDuplicates2(int[] nums) {
        int len = nums.length;
        int iter = 1;
        int pos = 1;
        int repeatNum = 0;
        int removeNum = 0;
        while (iter < len) {
            if (nums[iter] == nums[iter - 1]) {
                repeatNum++;
                if (repeatNum == 1) {
                    nums[pos] = nums[iter];
                    pos++;
                } else if (repeatNum > 1) {
                    removeNum++;
                }
            } else {
                nums[pos] = nums[iter];
                pos++;
                repeatNum = 0;
            }
            iter++;
        }
        return len - removeNum;
    }

    // 169. 多数元素
    public int majorityElement(int[] nums) {
        int len = nums.length;
        int nowNum = nums[0];
        int nowCount = 0;
        for (int i = 0; i < len; i++) {
            if (nowCount == 0) {
                nowNum = nums[i];
                nowCount++;
                continue;
            }
            if (nums[i] == nowNum) {
                nowCount++;
            } else {
                nowCount--;
            }
        }
        return nowNum;
    }

    // 189. 轮转数组
    public void rotate(int[] nums, int k) {
        int len = nums.length;
        k = k % len;
        reverse_of_189(nums, 0, len - k - 1);
        reverse_of_189(nums, len - k, len - 1);
        reverse_of_189(nums, 0, len - 1);
    }

    private void reverse_of_189(int[] nums, int start, int end) {
        while (start < end) {
            int temp = nums[start];
            nums[start] = nums[end];
            nums[end] = temp;
            start++;
            end--;
        }
    }

    // 121. 买卖股票的最佳时机
    public int maxProfit(int[] prices) {
        int len = prices.length;
        int[] buy = new int[len];
        int[] sell = new int[len];
        buy[0] = -prices[0];
        sell[0] = 0;
        for (int i = 1; i < len; i++) {
            buy[i] = Math.max(buy[i - 1], -prices[i]);
            sell[i] = Math.max(sell[i - 1], buy[i] + prices[i]);
        }
        return sell[len - 1];
    }

    // 22. 买卖股票的最佳时机 II
    public int maxProfit2(int[] prices) {
        int len = prices.length;
        int[] have = new int[len];
        int[] notHave = new int[len];
        have[0] = -prices[0];
        notHave[0] = 0;
        for (int i = 1; i < len; i++) {
            have[i] = Math.max(notHave[i - 1] - prices[i], have[i - 1]);
            notHave[i] = Math.max(notHave[i - 1], have[i - 1] + prices[i]);
        }
        return notHave[len - 1];
    }

    // 55. 跳跃游戏
    public boolean canJump(int[] nums) {
        int len = nums.length;
        int farest = 0;
        for (int i = 0; i < len; i++) {
            if (i > farest)
                return false;
            farest = Math.max(farest, i + nums[i]);
        }
        return true;
    }

    // 45. 跳跃游戏 II
    public int jump(int[] nums) {
        int len = nums.length;
        int jumps = 0;
        int thisJumpFarest = 0;
        int farest = 0;
        for (int i = 0; i < len; i++) {
            farest = Math.max(farest, i + nums[i]);
            if (i != len - 1 && i == thisJumpFarest) {
                jumps++;
                thisJumpFarest = farest;
            }
        }
        return jumps;
    }

    // 274. H 指数
    public int hIndex(int[] citations) {
        Arrays.sort(citations);
        int len = citations.length;
        int maxCites = 0;
        for (int i = 0; i < len; i++) {
            int nowCitation = citations[i];
            int nums = len - i;
            maxCites = Math.max(maxCites, Math.min(nowCitation, nums));
        }
        return maxCites;
    }

    static class RandomizedSet {

        Map<Integer, Integer> map;
        List<Integer> list;
        Random random;

        public RandomizedSet() {
            map = new HashMap<>();
            list = new ArrayList<>();
            random = new Random();
        }

        public boolean insert(int val) {
            if (map.containsKey(val))
                return false;
            list.add(val);
            map.put(val, list.size() - 1);
            return true;
        }

        public boolean remove(int val) {
            if (!map.containsKey(val))
                return false;
            int listPos = map.get(val);
            // 如果是list的最后一个元素，直接移除即可，如果不是，则和最后一个元素互换，然后移除
            if (listPos != list.size() - 1) {
                int lastVal = list.get(list.size() - 1);
                list.set(listPos, lastVal);
                map.put(lastVal, listPos);
            }
            list.remove(list.size() - 1);
            map.remove(val);
            return true;
        }

        public int getRandom() {
            int randomPos = random.nextInt(list.size());
            return list.get(randomPos);
        }
    }

    // 238. 除自身以外数组的乘积
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] left = new int[n];
        int[] right = new int[n];
        int[] answer = new int[n];
        left[0] = 1;
        for (int i = 1; i < n; i++) {
            left[i] = left[i - 1] * nums[i - 1];
        }
        right[n - 1] = 1;
        for (int i = n - 2; i >= 0; i--) {
            right[i] = right[i + 1] * nums[i + 1];
        }
        for (int i = 0; i < n; i++) {
            answer[i] = left[i] * right[i];
        }
        return answer;
    }

    // 134. 加油站
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int len = gas.length;
        int startPos = 0;
        while (startPos < len) {
            int pos = startPos;
            int haveGas = gas[pos];
            int haveLen = 0;
            while (haveGas >= cost[pos]) {
                haveLen++;
                haveGas -= cost[pos];
                pos = (pos + 1) % len;
                haveGas += gas[pos];
                if (haveLen == len)
                    return startPos;
            }
            startPos += haveLen + 1;
        }
        return -1;
    }

    // 135. 分发糖果
    public int candy(int[] ratings) {
        int len = ratings.length;
        int[] candies = new int[len];
        Arrays.fill(candies, 1);
        for (int i = 1; i < len; i++) {
            if (ratings[i] > ratings[i - 1])
                candies[i] = candies[i - 1] + 1;
        }
        for (int i = len - 2; i >= 0; i--) {
            if (ratings[i] > ratings[i + 1] && candies[i] <= candies[i + 1])
                candies[i] = candies[i + 1] + 1;
        }
        return Arrays.stream(candies).sum();
    }

    // 42. 接雨水
    public int trap(int[] height) {
        int left = 0, right = height.length - 1;
        int leftHeight = height[left], rightHeight = height[right];
        int sum = 0;
        while (left < right) {
            if (leftHeight < rightHeight) {
                int nextHeight = height[left + 1];
                if (nextHeight < leftHeight)
                    sum += leftHeight - nextHeight;
                else
                    leftHeight = nextHeight;
                left = left + 1;
            } else {
                int nextHeight = height[right - 1];
                if (nextHeight < rightHeight)
                    sum += rightHeight - nextHeight;
                else
                    rightHeight = nextHeight;
                right = right - 1;
            }
        }
        return sum;
    }

    // 13. 罗马数字转整数
    public int romanToInt(String s) {
        Map<Character, Integer> map = new HashMap<>();
        int[] value = new int[]{1, 5, 10, 50, 100, 500, 1000};
        map.put('I', 0);
        map.put('V', 1);
        map.put('X', 2);
        map.put('L', 3);
        map.put('C', 4);
        map.put('D', 5);
        map.put('M', 6);
        int ans = 0;
        int len = s.length();
        for (int i = len - 1; i >= 0; i--) {
            Character c = s.charAt(i);
            if (i < len - 1 && map.get(s.charAt(i + 1)) > map.get(c))
                ans -= value[map.get(c)];
            else
                ans += value[map.get(c)];
        }
        return ans;
    }

    // 12. 整数转罗马数字
    public String intToRoman(int num) {
        int[] possible = new int[]{1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
        StringBuilder sb = new StringBuilder();
        while (num > 0) {
            for (int i = 0; i < 13; i++) {
                if (num >= possible[i]) {
                    num -= possible[i];
                    switch (possible[i]) {
                        case 1000 -> sb.append("M");
                        case 900 -> sb.append("CM");
                        case 500 -> sb.append("D");
                        case 400 -> sb.append("CD");
                        case 100 -> sb.append("C");
                        case 90 -> sb.append("XC");
                        case 50 -> sb.append("L");
                        case 40 -> sb.append("XL");
                        case 10 -> sb.append("X");
                        case 9 -> sb.append("IX");
                        case 5 -> sb.append("V");
                        case 4 -> sb.append("IV");
                        case 1 -> sb.append("I");
                    }
                    break;
                }
            }
        }
        return sb.toString();
    }

    // 58. 最后一个单词的长度
    public int lengthOfLastWord(String s) {
        String trimmed = s.trim();
        int len = trimmed.length();
        int ans = 0;
        for (int i = len - 1; i >= 0; i--) {
            if (trimmed.charAt(i) == ' ')
                break;
            ans++;
        }
        return ans;
    }

    // 14. 最长公共前缀
    public String longestCommonPrefix(String[] strs) {
        StringBuilder sb = new StringBuilder();
        int minLen = Integer.MAX_VALUE;
        for (String str : strs) {
            minLen = Math.min(minLen, str.length());
        }
        int pos = 0;
        while (pos < minLen) {
            boolean isOK = true;
            for (int i = 1; i < strs.length; i++) {
                if (strs[i].charAt(pos) != strs[i - 1].charAt(pos)) {
                    isOK = false;
                    break;
                }
            }
            if (isOK) sb.append(strs[0].charAt(pos));
            else break;
            pos++;
        }
        return sb.toString();
    }

    // 151. 反转字符串中的单词
    public String reverseWords(String s) {
        s = s.trim();
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == ' ' && s.charAt(i - 1) == ' ')
                continue;
            sb.append(s.charAt(i));
        }
        s = sb.toString();
        String[] split = s.split(" ");
        sb = new StringBuilder();
        for (int i = split.length - 1; i >= 0; i--) {
            sb.append(split[i]);
            if (i != 0)
                sb.append(' ');
        }
        return sb.toString();
    }

    // 6. Z 字形变换
    public String convert(String s, int numRows) {
        //P   A   H   N
        //A P L S I I G
        //Y   I   R
        StringBuilder sb = new StringBuilder();
        int len = s.length();
        for (int i = 1; i <= numRows; i++) {
            int pos = i - 1;
            if (i == 1 || i == numRows) {
                int jump = Math.max((numRows - 1) * 2, 1);
                while (pos < len) {
                    sb.append(s.charAt(pos));
                    pos += jump;
                }
            } else {
                int jump1 = (numRows - i) * 2;
                int jump2 = (i - 1) * 2;
                boolean isJump1 = true;
                while (pos < len) {
                    sb.append(s.charAt(pos));
                    if (isJump1) {
                        isJump1 = false;
                        pos += jump1;
                    } else {
                        isJump1 = true;
                        pos += jump2;
                    }
                }
            }
        }
        return sb.toString();
    }

    // 28. 找出字符串中第一个匹配项的下标
    public int strStr(String haystack, String needle) {
        int len = haystack.length();
        int[] next = getNext(needle);
        int j = 0;
        for (int i = 0; i < len; i++) {
            while (j > 0 && haystack.charAt(i) != needle.charAt(j))
                j = next[j - 1];
            if (haystack.charAt(i) == needle.charAt(j))
                j++;
            if (j == next.length)
                return i - j + 1;
        }
        return -1;
    }

    private int[] getNext(String needle) {
        int len = needle.length();
        int[] next = new int[len];
        int j = 0;
        for (int i = 1; i < len; i++) {
            while (j > 0 && needle.charAt(i) != needle.charAt(j))
                j = next[j - 1];
            if (needle.charAt(i) == needle.charAt(j))
                j++;
            next[i] = j;
        }
        return next;
    }

    // 68. 文本左右对齐
    public List<String> fullJustify(String[] words, int maxWidth) {
        List<String> stringList = new ArrayList<>();
        int len = words.length;
        int nowLength = 0;
        int nowWordNum = 0;
        for (int i = 0; i < len; i++) {
            String nowWord = words[i];
            if (nowLength + words[i].length() + nowWordNum <= maxWidth) {
                nowLength += words[i].length();
                nowWordNum++;
            } else {
                StringBuilder sb = new StringBuilder();
                if (nowWordNum == 1) {
                    sb.append(words[i - 1]);
                    sb.append(" ".repeat(maxWidth - nowLength));
                } else {
                    int beginIndex = i - nowWordNum, endIndex = i - 1;
                    int allBlanks = maxWidth - nowLength;
                    int avgBlanks = allBlanks / (nowWordNum - 1);
                    int excessBlanks = allBlanks % (nowWordNum - 1);
                    while (beginIndex <= endIndex) {
                        sb.append(words[beginIndex]);
                        if (beginIndex != endIndex)
                            sb.append(" ".repeat(avgBlanks));
                        if (excessBlanks > 0) {
                            sb.append(" ");
                            excessBlanks--;
                        }
                        beginIndex++;
                    }
                }
                stringList.add(sb.toString());
                // 加入这一个
                nowLength = nowWord.length();
                nowWordNum = 1;
            }
            // 如果当前为最后一个单词，处理最后一行
            if (i == len - 1) {
                int beginIndex = i - nowWordNum + 1, endIndex = i;
                int endBlanks = maxWidth - nowLength - (nowWordNum - 1);
                StringBuilder sb = new StringBuilder();
                while (beginIndex <= endIndex) {
                    sb.append(words[beginIndex]);
                    if (beginIndex != endIndex)
                        sb.append(" ");
                    beginIndex++;
                }
                sb.append(" ".repeat(endBlanks));
                stringList.add(sb.toString());
            }
        }
        return stringList;
    }
}
